package net.tp.algo.graph.shortestpath;

import net.tp.algo.graph.Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * User: Trung
 * Date: 5/10/13
 * Time: 6:40 PM
 */
public class FloydWarshall {

    private final double[][] distance;
    private final int[][] midPoint;
    private boolean hasNegCycle;

    /**
     *
     * @param graph directed weighted graph with positive/negative edges. No negative cycle.
     */
    public FloydWarshall(Graph graph) {
        int N = graph.order();

        this.distance = new double[N][N];
        this.midPoint = new int[N][N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(distance[i], Double.MAX_VALUE);
            Arrays.fill(midPoint[i], -1);
            distance[i][i] = 0;
        }

        for (int u = 0; u < N; u++) {
            for (Graph.Edge edge : graph.edges(u)) {
                int w = edge.other(u);
                distance[u][w] = edge.weight();
            }
        }

        this.hasNegCycle = false;

        loop:
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (distance[i][k] < Double.MAX_VALUE && distance[k][j] < Double.MAX_VALUE &&
                            distance[i][k] + distance[k][j] < distance[i][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                        midPoint[i][j] = k;

                        if (i==j && distance[i][j] < 0) {
                            hasNegCycle = true;
                            break loop;
                        }
                    }
                }
            }
        }

    }

    public double distance(int u, int w) {
        if (this.hasNegCycle) {
            throw new IllegalArgumentException("Negative cycle detected.");
        }
        return distance[u][w];
    }

    public List<Integer> path(int u, int w) {
        if (this.hasNegCycle) {
            throw new IllegalArgumentException("Negative cycle detected.");
        }

        if (distance[u][w] == Double.MAX_VALUE) {
            return Collections.emptyList();
        }

        if (u == w) {
            return Collections.singletonList(u);
        }

        List<Integer> path = _findPath(u, w);
        path.add(w);

        return path;
    }

    private List<Integer> _findPath(int u, int w) {
        assert u != w;

        int k = midPoint[u][w];
        if (k == -1) {
            return Collections.singletonList(u);
        }

        List<Integer> result = new ArrayList<>();
        result.addAll(_findPath(u, k));
        result.addAll(_findPath(k, w));

        return result;
    }

}
